﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Inspired.Euler
{
    /// <summary>
    /// In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:
    /// 
    /// 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
    /// It is possible to make £2 in the following way:
    /// 
    /// 1 x £1 + 1 x 50p + 2 x 20p + 1 x 5p + 1 x 2p + 3 x 1p
    /// How many different ways can £2 be made using any number of coins?
    /// </summary>
    public static class Problem031
    {
        /// <summary>
        /// Investigating combinations of English currency denominations.
        /// </summary>
        public static long Solve()
        {
            Dictionary<int, Dictionary<int, int>> changes = new Dictionary<int, Dictionary<int, int>>();
            long ways = 0;
            int amount = 200;

            for (int c200 = amount; c200 >= 0; c200 -= 200)
                for (int c100 = c200; c100 >= 0; c100 -= 100)
                    for (int c50 = c100; c50 >= 0; c50 -= 50)
                        for (int c20 = c50; c20 >= 0; c20 -= 20)
                            for(int c10 = c20; c10 >= 0; c10 -= 10)
                                for (int c05 = c10; c05 >= 0; c05 -= 05)
                                    for (int c02 = c05; c02 >= 0; c02 -= 02)
                                        ways++;

            return ways; // 73682

            //To calculate each entry, you start with the pennies.
            // There is exactly one way to make change for every amount.
            // Then calculate the .05 row by 
            //     adding  the number of ways to make change for the amount using pennies 
            //     plus the number of ways to make change for five cents 
            //     less using nickels and pennies.  
            // This continues on for all denominations of coins.  

            // http://home.att.net/~numericana/answer/counting.htm
            // http://faqs.cs.uu.nl/na-dir/puzzles/archive/combinatorics.html
            // http://books.google.com.br/books?id=C-0y7LI2FFMC&pg=PA176&lpg=PA176&dq=combinatorics+coins+cents+change&source=bl&ots=hBoZq9Faqb&sig=5amrFTU8ZE6umLhjx749UTjgqZ8&hl=pt-BR&ei=ml8NS5SbFsaWtgetl7jqAg&sa=X&oi=book_result&ct=result&resnum=4&ved=0CBwQ6AEwAw#v=onepage&q=&f=false
            // http://www.cut-the-knot.org/ctk/GeneratingFunctions.shtml
            ways = 0;
            int[] coins = new[] { 1, 2, 5, 10, 20, 50, 100, 200 };
            foreach (int coin in coins) 
            {
                changes.Add(coin, new Dictionary<int, int>());
                for (int k = 1; k <= amount; k++) 
                {
                    //changes[coin].Add(k, changes[k][last] + 1);
                    //last = coin;
                }
            }
            return changes[coins.Last()][amount];
        }
    }
}
